package com.zlk.algorithm.dataStructure.graph.traverse;

import com.zlk.algorithm.dataStructure.graph.impl.Graph;
import com.zlk.algorithm.dataStructure.graph.impl.Node;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack;

/**
 * @program: algorithm
 * @ClassName DFS
 * @description: 深度优先遍历 利用栈和set
 * @author: slfang
 * @create: 2024-03-15 17:03
 * @Version 1.0
 **/
public class DFS {


    public void dfs(Node node){
        if(node==null){
            return ;
        }
        HashSet<Node> set  = new HashSet<>();
        Stack<Node> stack = new Stack<>();
        stack.add(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            for (Node next : pop.nexts) {
                if(!set.contains(next)){
                    set.add(next);
                    stack.add(pop);
                    stack.add(next);
                    System.out.println(next.value);
                    break;//只要找到一个就继续往下层找，不在此层所以是break
                }
            }
        }

    }

    @Test
    public void test() {
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node21 = new Node(2);
        Node node22 = new Node(2);
        Node node31 = new Node(3);
        Node node41 = new Node(4);

        ArrayList<Node> list1 = new ArrayList();
        ArrayList<Node> list2 = new ArrayList();
        ArrayList<Node> list3 = new ArrayList();
        list1.add(node21);
        list1.add(node22);
        node1.nexts = list1;

        list2.add(node31);
        list3.add(node41);


        node22.nexts = list2;
        node31.nexts = list3;
        dfs(node1);


    }



}
